package com.xypower.sort;

//归并排序
public class MergeSortTest {
    public static void mergeSort(int[] arr){
        if (arr ==null || arr.length<2){
            return;
        }
        process(arr,0,arr.length-1);
    }



    public static void process(int[] arr,int L,int R){
        if (L==R){
            return;
        }
        int mid = L + ((R-L) >> 1);             //求中点
        process(arr,L,mid);                     //调用自己
        process(arr,mid+1,R);                //由master函数可知时间复杂度为o(N*logN)
        merge(arr,L,mid,R);
    }

    public static void merge(int[] arr,int L,int M,int R){
        int[] help = new int[R - L + 1];    //额外的时间复杂度o(N)
        int i =0;
        int p1 = L;
        int p2 = M+1;
        while (p1 <=M && p2 <=R){   //都没越界
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        //剩下的没越界全部拷贝到help中 
        while (p1 <= M){
            help[i++] = arr[p1++];
        }
        while (p2 <= R){
            help[i++] = arr[p2++];
        }
        for (i=0;i<help.length;i++){
            arr[L+1] = help[i];
        }
    }
}
